The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0, cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0) → 01
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0, cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0) → 01
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Rewrite Strategy: INNERMOST

(1) RenamingProof (EQUIVALENT transformation)

Renamed function symbols to avoid clashes with predefined symbol.

(2) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

S is empty.
Rewrite Strategy: INNERMOST

(3) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(4) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

(5) OrderProof (LOWER BOUND(ID) transformation)

Heuristically decided to analyse the following defined symbols:
dbl, dbls, sel, indx, from, dbl1, sel1, quote

They will be analysed ascendingly in the following order:
dbl < dbls
sel < indx
dbl1 < quote
sel1 < quote

(6) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

The following defined symbols remain to be analysed:
dbl, dbls, sel, indx, from, dbl1, sel1, quote

They will be analysed ascendingly in the following order:
dbl < dbls
sel < indx
dbl1 < quote
sel1 < quote

(7) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

Induction Base:
dbl(gen_0':s:01':s13_0(0)) →_R^Ω(1)
0'

Induction Step:
dbl(gen_0':s:01':s13_0(+(n6_0, 1))) →_R^Ω(1)
s(s(dbl(gen_0':s:01':s13_0(n6_0)))) →_IH
s(s(gen_0':s:01':s13_0(*(2, c7_0))))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(8) Complex Obligation (BEST)

(9) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

The following defined symbols remain to be analysed:
dbls, sel, indx, from, dbl1, sel1, quote

They will be analysed ascendingly in the following order:
sel < indx
dbl1 < quote
sel1 < quote

(10) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)

Induction Base:
dbls(gen_nil:cons4_0(0)) →_R^Ω(1)
nil

Induction Step:
dbls(gen_nil:cons4_0(+(n334_0, 1))) →_R^Ω(1)
cons(dbl(0'), dbls(gen_nil:cons4_0(n334_0))) →_L^Ω(1)
cons(gen_0':s:01':s13_0(*(2, 0)), dbls(gen_nil:cons4_0(n334_0))) →_IH
cons(gen_0':s:01':s13_0(0), gen_nil:cons4_0(c335_0))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(11) Complex Obligation (BEST)

(12) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

The following defined symbols remain to be analysed:
sel, indx, from, dbl1, sel1, quote

They will be analysed ascendingly in the following order:
sel < indx
dbl1 < quote
sel1 < quote

(13) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)

Induction Base:
sel(gen_0':s:01':s13_0(0), gen_nil:cons4_0(+(1, 0))) →_R^Ω(1)
0'

Induction Step:
sel(gen_0':s:01':s13_0(+(n751_0, 1)), gen_nil:cons4_0(+(1, +(n751_0, 1)))) →_R^Ω(1)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) →_IH
gen_0':s:01':s13_0(0)

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(14) Complex Obligation (BEST)

(15) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

The following defined symbols remain to be analysed:
indx, from, dbl1, sel1, quote

They will be analysed ascendingly in the following order:
dbl1 < quote
sel1 < quote

(16) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1)) → gen_nil:cons4_0(n1186_0), rt ∈ Ω(1 + n1186₀)

Induction Base:
indx(gen_nil:cons4_0(0), gen_nil:cons4_0(1)) →_R^Ω(1)
nil

Induction Step:
indx(gen_nil:cons4_0(+(n1186_0, 1)), gen_nil:cons4_0(1)) →_R^Ω(1)
cons(sel(0', gen_nil:cons4_0(1)), indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1))) →_L^Ω(1)
cons(gen_0':s:01':s13_0(0), indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1))) →_IH
cons(gen_0':s:01':s13_0(0), gen_nil:cons4_0(c1187_0))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(17) Complex Obligation (BEST)

(18) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)
indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1)) → gen_nil:cons4_0(n1186_0), rt ∈ Ω(1 + n1186₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

The following defined symbols remain to be analysed:
from, dbl1, sel1, quote

They will be analysed ascendingly in the following order:
dbl1 < quote
sel1 < quote

(19) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol from.

(20) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)
indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1)) → gen_nil:cons4_0(n1186_0), rt ∈ Ω(1 + n1186₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

The following defined symbols remain to be analysed:
dbl1, sel1, quote

They will be analysed ascendingly in the following order:
dbl1 < quote
sel1 < quote

(21) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol dbl1.

(22) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)
indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1)) → gen_nil:cons4_0(n1186_0), rt ∈ Ω(1 + n1186₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

The following defined symbols remain to be analysed:
sel1, quote

They will be analysed ascendingly in the following order:
sel1 < quote

(23) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
sel1(gen_0':s:01':s13_0(n2395_0), gen_nil:cons4_0(+(1, n2395_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n2395₀)

Induction Base:
sel1(gen_0':s:01':s13_0(0), gen_nil:cons4_0(+(1, 0))) →_R^Ω(1)
0'

Induction Step:
sel1(gen_0':s:01':s13_0(+(n2395_0, 1)), gen_nil:cons4_0(+(1, +(n2395_0, 1)))) →_R^Ω(1)
sel1(gen_0':s:01':s13_0(n2395_0), gen_nil:cons4_0(+(1, n2395_0))) →_IH
gen_0':s:01':s13_0(0)

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(24) Complex Obligation (BEST)

(25) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)
indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1)) → gen_nil:cons4_0(n1186_0), rt ∈ Ω(1 + n1186₀)
sel1(gen_0':s:01':s13_0(n2395_0), gen_nil:cons4_0(+(1, n2395_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n2395₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

The following defined symbols remain to be analysed:
quote

(26) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol quote.

(27) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)
indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1)) → gen_nil:cons4_0(n1186_0), rt ∈ Ω(1 + n1186₀)
sel1(gen_0':s:01':s13_0(n2395_0), gen_nil:cons4_0(+(1, n2395_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n2395₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

No more defined symbols left to analyse.

(28) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

(29) BOUNDS(n^1, INF)

(30) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)
indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1)) → gen_nil:cons4_0(n1186_0), rt ∈ Ω(1 + n1186₀)
sel1(gen_0':s:01':s13_0(n2395_0), gen_nil:cons4_0(+(1, n2395_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n2395₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

No more defined symbols left to analyse.

(31) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

(32) BOUNDS(n^1, INF)

(33) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)
indx(gen_nil:cons4_0(n1186_0), gen_nil:cons4_0(1)) → gen_nil:cons4_0(n1186_0), rt ∈ Ω(1 + n1186₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

No more defined symbols left to analyse.

(34) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

(35) BOUNDS(n^1, INF)

(36) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)
sel(gen_0':s:01':s13_0(n751_0), gen_nil:cons4_0(+(1, n751_0))) → gen_0':s:01':s13_0(0), rt ∈ Ω(1 + n751₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

No more defined symbols left to analyse.

(37) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

(38) BOUNDS(n^1, INF)

(39) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)
dbls(gen_nil:cons4_0(n334_0)) → gen_nil:cons4_0(n334_0), rt ∈ Ω(1 + n334₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

No more defined symbols left to analyse.

(40) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

(41) BOUNDS(n^1, INF)

(42) Obligation:

Innermost TRS:
Rules:
dbl(0') → 0'
dbl(s(X)) → s(s(dbl(X)))
dbls(nil) → nil
dbls(cons(X, Y)) → cons(dbl(X), dbls(Y))
sel(0', cons(X, Y)) → X
sel(s(X), cons(Y, Z)) → sel(X, Z)
indx(nil, X) → nil
indx(cons(X, Y), Z) → cons(sel(X, Z), indx(Y, Z))
from(X) → cons(X, from(s(X)))
dbl1(0') → 01'
dbl1(s(X)) → s1(s1(dbl1(X)))
sel1(0', cons(X, Y)) → X
sel1(s(X), cons(Y, Z)) → sel1(X, Z)
quote(0') → 01'
quote(s(X)) → s1(quote(X))
quote(dbl(X)) → dbl1(X)
quote(sel(X, Y)) → sel1(X, Y)

Types:
dbl :: 0':s:01':s1 → 0':s:01':s1
0' :: 0':s:01':s1
s :: 0':s:01':s1 → 0':s:01':s1
dbls :: nil:cons → nil:cons
nil :: nil:cons
cons :: 0':s:01':s1 → nil:cons → nil:cons
sel :: 0':s:01':s1 → nil:cons → 0':s:01':s1
indx :: nil:cons → nil:cons → nil:cons
from :: 0':s:01':s1 → nil:cons
dbl1 :: 0':s:01':s1 → 0':s:01':s1
01' :: 0':s:01':s1
s1 :: 0':s:01':s1 → 0':s:01':s1
sel1 :: 0':s:01':s1 → nil:cons → 0':s:01':s1
quote :: 0':s:01':s1 → 0':s:01':s1
hole_0':s:01':s11_0 :: 0':s:01':s1
hole_nil:cons2_0 :: nil:cons
gen_0':s:01':s13_0 :: Nat → 0':s:01':s1
gen_nil:cons4_0 :: Nat → nil:cons

Lemmas:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

Generator Equations:
gen_0':s:01':s13_0(0) ⇔ 0'
gen_0':s:01':s13_0(+(x, 1)) ⇔ s(gen_0':s:01':s13_0(x))
gen_nil:cons4_0(0) ⇔ nil
gen_nil:cons4_0(+(x, 1)) ⇔ cons(0', gen_nil:cons4_0(x))

No more defined symbols left to analyse.

(43) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
dbl(gen_0':s:01':s13_0(n6_0)) → gen_0':s:01':s13_0(*(2, n6_0)), rt ∈ Ω(1 + n6₀)

(44) BOUNDS(n^1, INF)